# sadly, this is slow
import copy
class Solution:
	# @return a list of lists of integers
	def combine(self, n, k):
		temp = {}
		return self.__combine(n, k, temp)

	def __combine(self, n, k, temp):
		if n < k:
			return []
		if n == k:
			if (n,n) in temp:
				return copy.deepcopy(temp[(n,n)])
			else:
 				s1 = [range(1, n+1)]
				temp[(n,n)] = copy.deepcopy(s1)
				return s1
		if n > k:
			if k == 1:
				return [[i] for i in xrange(1, n+1)]
			else:
				if (n-1, k) in temp:
					base = copy.deepcopy(temp[(n-1, k)])
				else:
					base = self.__combine(n-1, k, temp)
					temp[(n-1, k)] = copy.deepcopy(base)
				for lin in self.__combine(n-1, k-1, temp):
					z = copy.deepcopy(lin)
					z.append(n)
					base.append(z)
				return copy.deepcopy(base)




if __name__ == '__main__':
	so = Solution()
	print so.combine(5,3)